public class Solution110 {

    class Pair<L, R>{
        public L leftValue;
        public R rightValue;

        public Pair(L leftValue, R rightValue) {
            this.leftValue = leftValue;
            this.rightValue = rightValue;
        }
    }

    private Pair<Boolean, Integer> getIsBalanceAndHeight(TreeNode node){
        if(node == null){
            return new Pair<>(true, 0);
        }
        Pair<Boolean, Integer> leftRes = getIsBalanceAndHeight(node.left);
        Pair<Boolean, Integer> rightRes = getIsBalanceAndHeight(node.right);
        boolean isBalance = leftRes.leftValue && rightRes.leftValue && Math.abs(leftRes.rightValue - rightRes.rightValue) <= 1;
        int height = Math.max(leftRes.rightValue, rightRes.rightValue) + 1;
        return new Pair<>(isBalance, height);
    }

    public boolean isBalanced(TreeNode root) {
        return getIsBalanceAndHeight(root).leftValue;
    }
}
